How can we predict the difficulty of a Sudoku puzzle? We give an overview ofdifficulty rating metrics and evaluate them on extensive dataset on humanproblem solving (more then 1700 Sudoku puzzles, hundreds of solvers). The bestresults are obtained using a computational model of human solving activity.Using the model we show that there are two sources of the problem difficulty:complexity of individual steps (logic operations) and structure of dependencyamong steps. We also describe metrics based on analysis of solutions underrelaxed constraints -- a novel approach inspired by phase transition phenomenonin the graph coloring problem. In our discussion we focus not just on theperformance of individual metrics on the Sudoku puzzle, but also on theirgeneralizability and applicability to other problems.
展开▼
